InforLorV4, Main, Exploration, bibRecord, 001E88

Scheduling an unbounded batching machine with job processing time compatibilities

Identifieur interne : 001E88 ( Main/Exploration ); précédent : 001E87; suivant : 001E89

Scheduling an unbounded batching machine with job processing time compatibilities

Auteurs : A. Bellanger [France] ; A. Janiak [Pologne] ; M. Y. Kovalyov [Biélorussie] ; A. Oulamara [France]

Source :

Discrete applied mathematics [ 0166-218X ] ; 2012.

RBID : Pascal:12-0046320

Descripteurs français

Pascal (Inist)
- Informatique théorique, Optimisation, Combinatoire, Ordonnancement, Temps traitement, Compatibilité, Fonction objectif, Intervalle temps, Traitement par lot, Intersection, Horaire, Algorithme, Complétion, Minimisation, Programmation dynamique, Temps total achèvement, Maximum, Complexité, 68M20, 68Wxx, 49Lxx.

English descriptors

KwdEn :
- Algorithm, Batch processing, Combinatorics, Compatibility, Completion, Complexity, Computer theory, Dynamic programming, Intersection, Makespan, Maximum, Minimization, Objective function, Optimization, Processing time, Schedule, Scheduling, Time interval.

Abstract

The problem of scheduling n jobs on an unbounded batching machine to minimize a regular objective function is studied. In this problem intervals for job processing times are given. The machine can process any number of jobs in a batch, provided that the processing time intervals of these jobs have a non-empty intersection. The jobs in the same batch start and complete together, and the batch processing time is equal to the left endpoint of the intersection of the processing time intervals in this batch. Properties of an optimal schedule are established and an enumerative algorithm based on these properties is developed. For the total completion time minimization, a dynamic programming algorithm is developed. Minimizing the makespan is shown to be solvable in 0(n log n) time and minimizing the maximum lateness is proved to be NP-hard.

Affiliations:

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: 000128
to stream PascalFrancis, to step Curation: 000883
to stream PascalFrancis, to step Checkpoint: 000101
to stream Main, to step Merge: 001F10
to stream Main, to step Curation: 001E88

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Scheduling an unbounded batching machine with job processing time compatibilities</title>
<author><name sortKey="Bellanger, A" sort="Bellanger, A" uniqKey="Bellanger A" first="A." last="Bellanger">A. Bellanger</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Nancy University, LORIA laboratory, Ecole des Mines de Nancy, Parc de Saurupt</s1>
<s2>54042 Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Janiak, A" sort="Janiak, A" uniqKey="Janiak A" first="A." last="Janiak">A. Janiak</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Institute of Engineering Cybernetics, Wroclaw University of Technology, Janiszewskiego 11/17</s1>
<s2>50-372 Wroclaw</s2>
<s3>POL</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Pologne</country>
<wicri:noRegion>50-372 Wroclaw</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Kovalyov, M Y" sort="Kovalyov, M Y" uniqKey="Kovalyov M" first="M. Y." last="Kovalyov">M. Y. Kovalyov</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6</s1>
<s2>220012 Minsk</s2>
<s3>BLR</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>Biélorussie</country>
<wicri:noRegion>220012 Minsk</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Oulamara, A" sort="Oulamara, A" uniqKey="Oulamara A" first="A." last="Oulamara">A. Oulamara</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Nancy University, LORIA laboratory, Ecole des Mines de Nancy, Parc de Saurupt</s1>
<s2>54042 Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">12-0046320</idno>
<date when="2012">2012</date>
<idno type="stanalyst">PASCAL 12-0046320 INIST</idno>
<idno type="RBID">Pascal:12-0046320</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000128</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000883</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000101</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000101</idno>
<idno type="wicri:doubleKey">0166-218X:2012:Bellanger A:scheduling:an:unbounded</idno>
<idno type="wicri:Area/Main/Merge">001F10</idno>
<idno type="wicri:Area/Main/Curation">001E88</idno>
<idno type="wicri:Area/Main/Exploration">001E88</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Scheduling an unbounded batching machine with job processing time compatibilities</title>
<author><name sortKey="Bellanger, A" sort="Bellanger, A" uniqKey="Bellanger A" first="A." last="Bellanger">A. Bellanger</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Nancy University, LORIA laboratory, Ecole des Mines de Nancy, Parc de Saurupt</s1>
<s2>54042 Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Janiak, A" sort="Janiak, A" uniqKey="Janiak A" first="A." last="Janiak">A. Janiak</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Institute of Engineering Cybernetics, Wroclaw University of Technology, Janiszewskiego 11/17</s1>
<s2>50-372 Wroclaw</s2>
<s3>POL</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Pologne</country>
<wicri:noRegion>50-372 Wroclaw</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Kovalyov, M Y" sort="Kovalyov, M Y" uniqKey="Kovalyov M" first="M. Y." last="Kovalyov">M. Y. Kovalyov</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6</s1>
<s2>220012 Minsk</s2>
<s3>BLR</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>Biélorussie</country>
<wicri:noRegion>220012 Minsk</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Oulamara, A" sort="Oulamara, A" uniqKey="Oulamara A" first="A." last="Oulamara">A. Oulamara</name>
<affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Nancy University, LORIA laboratory, Ecole des Mines de Nancy, Parc de Saurupt</s1>
<s2>54042 Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Nancy</settlement>
</placeName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Discrete applied mathematics</title>
<title level="j" type="abbreviated">Discrete appl. math.</title>
<idno type="ISSN">0166-218X</idno>
<imprint><date when="2012">2012</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Discrete applied mathematics</title>
<title level="j" type="abbreviated">Discrete appl. math.</title>
<idno type="ISSN">0166-218X</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Batch processing</term>
<term>Combinatorics</term>
<term>Compatibility</term>
<term>Completion</term>
<term>Complexity</term>
<term>Computer theory</term>
<term>Dynamic programming</term>
<term>Intersection</term>
<term>Makespan</term>
<term>Maximum</term>
<term>Minimization</term>
<term>Objective function</term>
<term>Optimization</term>
<term>Processing time</term>
<term>Schedule</term>
<term>Scheduling</term>
<term>Time interval</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Informatique théorique</term>
<term>Optimisation</term>
<term>Combinatoire</term>
<term>Ordonnancement</term>
<term>Temps traitement</term>
<term>Compatibilité</term>
<term>Fonction objectif</term>
<term>Intervalle temps</term>
<term>Traitement par lot</term>
<term>Intersection</term>
<term>Horaire</term>
<term>Algorithme</term>
<term>Complétion</term>
<term>Minimisation</term>
<term>Programmation dynamique</term>
<term>Temps total achèvement</term>
<term>Maximum</term>
<term>Complexité</term>
<term>68M20</term>
<term>68Wxx</term>
<term>49Lxx</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">The problem of scheduling n jobs on an unbounded batching machine to minimize a regular objective function is studied. In this problem intervals for job processing times are given. The machine can process any number of jobs in a batch, provided that the processing time intervals of these jobs have a non-empty intersection. The jobs in the same batch start and complete together, and the batch processing time is equal to the left endpoint of the intersection of the processing time intervals in this batch. Properties of an optimal schedule are established and an enumerative algorithm based on these properties is developed. For the total completion time minimization, a dynamic programming algorithm is developed. Minimizing the makespan is shown to be solvable in 0(n log n) time and minimizing the maximum lateness is proved to be NP-hard.</div>
</front>
</TEI>
<affiliations><list><country><li>Biélorussie</li>
<li>France</li>
<li>Pologne</li>
</country>
<region><li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<settlement><li>Nancy</li>
</settlement>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Bellanger, A" sort="Bellanger, A" uniqKey="Bellanger A" first="A." last="Bellanger">A. Bellanger</name>
</region>
<name sortKey="Oulamara, A" sort="Oulamara, A" uniqKey="Oulamara A" first="A." last="Oulamara">A. Oulamara</name>
</country>
<country name="Pologne"><noRegion><name sortKey="Janiak, A" sort="Janiak, A" uniqKey="Janiak A" first="A." last="Janiak">A. Janiak</name>
</noRegion>
</country>
<country name="Biélorussie"><noRegion><name sortKey="Kovalyov, M Y" sort="Kovalyov, M Y" uniqKey="Kovalyov M" first="M. Y." last="Kovalyov">M. Y. Kovalyov</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001E88 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001E88 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Pascal:12-0046320
   |texte=   Scheduling an unbounded batching machine with job processing time compatibilities
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

Scheduling an unbounded batching machine with job processing time compatibilities

Scheduling an unbounded batching machine with job processing time compatibilities

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri